#include "Clustering.h"

#include <stdlib.h>
#include <math.h>
#include "lib/csim.h"
#include "QueueNetworkModel.h"
#include "Config.h"
#include "StochasticModel.h"

int comparePRequest(PartitionedRequest* a, PartitionedRequest *b){
    if(a->size == b->size){
        return 0;
    }else if(a->size > b->size){
        return 1;
    }
    return -1;
}

PartitionedRequest * getMaximalPoint(){
    int i;
    PartitionedRequest * max = &p_request[0];

    for(i=0; i<N_P_REQUEST; i++){
        if(comparePRequest(max, &p_request[i])<0){
            max = &p_request[i];
        }
    }
    return max;
}

PartitionedRequest * getMinimalPoint(){
    int i;
    PartitionedRequest * min = &p_request[0];

    for(i=0; i<N_P_REQUEST; i++){
        if(comparePRequest(min, &p_request[i])>0){
            min = &p_request[i];
        }
    }
    return min;
}

int myrand(int max) {
    int x = rand()%max;
    return x;
}

void initializeCentroid(KMeansCluster * cluster, int n_class){
    int i;
    
#if STOCHASTIC_CLUSTERIZED_SIZE
    srand(SEED_STOCHASTIC_SIZE_CLUSTERING);
#else
    srand(SEED_TRACE_STOCHASTIC_CLUSTERING);
#endif

    range = maximal_point->size - minimal_point->size;

    for(i=0; i<n_class; i++){
        cluster[i].center = cumulative_distribution[myrand(N_SIZE)]->size;
        cluster[i].sum = 0;
        cluster[i].n_item =0 ;
        cluster[i].class_id = i;
        cluster[i].probability_element=0;
        cluster[i].standard_deviation=0;
    }
}

void resetCentroids(KMeansCluster * cluster, int n_class){
    int i;
    for(i=0; i<n_class; i++){
        cluster[i].sum = 0;
        cluster[i].n_item = 0 ;
        cluster[i].probability_element = 0;
        cluster[i].standard_deviation = 0;
    }
}

void getClusterMembership(PartitionedRequest *r, KMeansCluster * c, int n_class){
    int i, ctrl = 0, ctrl2 = 0;
    KMeansCluster *ret = NULL;
    double delta, min = (double)max ;

    for(i=0; i<n_class; i++){
        ctrl2++;
        delta = fabs(c[i].center - (double)r->size);
        if(delta < min){
            ctrl++;
            min = delta;
            ret = &c[i];
        }
    }

    r->p_class = ret->class_id;
}

void computeClusterMembership(PartitionedRequest * r, KMeansCluster * c, int n_class ){
    int i;
    KMeansCluster * ret;
    double delta, min = maximal_point->size ;

    for(i=0; i<n_class; i++){
        delta = fabs(c[i].center - (double)r->size);
        if(delta < min){
            min = delta;
            ret = &c[i];
        }
    }

    r->p_class = ret->class_id;
    ret->n_item++;
    ret->sum += r->size;
}

void computeClusterStats(KMeansCluster * c, int n_class){
    int i;
    double sum_dev =0;
    double deviation[n_class];

    for(i=0; i<N_P_REQUEST; i++) {
        sum_dev = p_request[i].size - c[p_request[i].p_class].center;
        sum_dev *= sum_dev;
        deviation[p_request[i].p_class] += sum_dev;
    }

    for(i=0; i<n_class; i++) {
        deviation[i] /= c[i].n_item;
        c[i].standard_deviation = sqrt(deviation[i]);
        c[i].probability_element = c[i].n_item/(double)N_P_REQUEST;
    }
}

CoefficentVariation computeCoefficentVariation(KMeansCluster *c, int n_class){
    int i,j;
    CoefficentVariation cv = {0,0,0};
    for(i=0; i<n_class; i++)
        for(j=i+1; j<n_class; j++) {
            cv.intercluster += (fabs(c[j].center - c[i].center))/(double)(n_class*(n_class-1)/2);
        }
    for(i=0; i<N_P_REQUEST; i++)
        cv.intracluster += (fabs(p_request[i].size - c[p_request[i].p_class].center))/N_P_REQUEST;

    cv.beta_cv = cv.intracluster/cv.intercluster;
    return cv;
}

void updateCentroids(int n_class) {
    int i;
    for (i=0; i<n_class; i++) {
        if (cluster[i].n_item != 0)
                cluster[i].center = cluster[i].sum / (double)cluster[i].n_item;
    }
}

void saveCentroids(int n_class) {
    int i;
    for (i=0; i<n_class; i++)
        centroids[i] = cluster[i].center;
}

int compareCentroids(int n_class) {
    int i, c=0;
    for (i=0; i<n_class; i++) {
        if (cluster[i].center == centroids[i])
            c++;
    }
    if (c == n_class)
        return 1;
    return 0;
}

void printCluster(int n_class) {
    int i;
    for (i=0; i<n_class; i++)
        printf("Centroide[%d]:\t%f\tItem:\t%lu\n", i, cluster[i].center, cluster[i].n_item);
    printf("\n");
}

double computeKMeansClustering(int n_class) {
    printf("Compute Clustering with KMeans Algorithm (k=%d)\n", n_class);
    unsigned long i;

    cluster = (KMeansCluster *)malloc(sizeof (KMeansCluster) * n_class);
    centroids = (double*)malloc(sizeof(double)*n_class);

    maximal_point = getMaximalPoint();
    minimal_point = getMinimalPoint();

    max = maximal_point->size;

    initializeCentroid(cluster, n_class);

    int iteration = 0;
    double is_not_modified = 0;

    for (i=0; i<n_class; i++)
        centroids[i] = 0;

    do {
        saveCentroids(n_class);
        resetCentroids(cluster, n_class);
        is_not_modified = 1;

        for (i = 0; i < N_P_REQUEST; i++)
            computeClusterMembership(&p_request[i], cluster, n_class);

        updateCentroids(n_class);
        iteration++;
        printf(".");
    } while (!compareCentroids(n_class));

    CoefficentVariation cv = computeCoefficentVariation(cluster, n_class);
    computeClusterStats(cluster, n_class);

    printf("\n");
    
    printCluster(n_class);
    printf("Clustering Finished: Converged in %d iterations with a betaCV: %f\n", iteration, cv.beta_cv);
    return 0;
}